/**
 * @author 徐楠
 * @date 2022/1/23 11:30
 * @version 1.0
 */

package com.xunan.likou;

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        String s = "ac";
        String result = longestPalindrome1(s);
        System.out.println(result);
    }

    public static String longestPalindrome(String s) {

        return null;
    }

    /**************************
     * 求解字符串的最长回文串----暴力法 O(n^3)
     * 通过两层循环找出字符串的所有子串  对每一个子串进行判断
     * 将是回文串的子串储存  当有新的回文串时，比较记录中的回文串和当前回文串的长度
     * 用较长的串替换当前串  如果两串长度相同，保留旧的
     * PS：如果想保存所有的回文串 可以修改记录回文串的结构为String数组（链表、hash表都可以）
     * @param s 要求解的字符串
     * @return 返回字符串中的最长回文串
     */
    public static String longestPalindrome1(String s) {
        //非空判断
        if ((s == null) || s.length() == 0) {
            return null;
        }
        //将字符串转换为字符数组
        char[] oriArray = s.toCharArray();
        int first = 0;
        int end = 0;//当前字符串中回文串的始末位置 包含末位置

        for (int i = 0; i < oriArray.length - 1; i++)//两次循环 查找字符串的所有子串
        {
            for (int j = i; j < oriArray.length; j++) {
                //判断子串是否为回文串
                int left = i, right = j;//记录左侧右侧的位置
                while (left < right)//左侧下标小于右侧下标时 比较未完成
                {
                    if (oriArray[left] != oriArray[right])
                        break;//如果出现对称位置不相等元素  则不是回文串跳出循环
                    //判断下一对称位置
                    left++;
                    right--;

                }
                if (left >= right)//是否比较完成 是字符串是否为回文串的判断条件
                {
                    if (j - i > end - first)//查找到回文串 且长度大于当前存储的回文串长度
                    {
                        //替换当前回文串
                        first = i;
                        end = j;
                    }
                }
			/*if(isPlalindrome(oriArray,i,j))//是回文串
			{
				if(j-i>end-first)//查找到回文串
				{
					//替换当前回文串
					first=i;
					end=j;
				}
			}*/
            }
        }
        //查找结束  将数组转化为字符串返回
        return String.valueOf(oriArray, first, end - first + 1);
    }

    /*****************************
     * 求解字符串中的最长回文串 -----中心拓展法O(n^2)
     * 基本思路  选择一个字符作为中心 向两边查找回文串
     * 但是查找过程中需要将长度为奇数的回文串和长度为偶数的回文串分开考虑
     * @param original 要求解的字符串
     * @return 返回字符串中的最长回文串
     */
    public static String longestPalindrome2(String original) {
        //非空判断
        if ((original == null) || original.length() == 0) {
            return null;
        }
        //将字符串转换为字符数组
        char[] oriArray = original.toCharArray();
        int first = 0;
        int end = 0;//当前字符串中回文串的始末位置 包括末位置

        //查找奇数位的回文串
        for (int i = 0; i < oriArray.length; i++) {
            //i为中心点  从i开始向两边进行判断
            int preI = i - 1, sufI = i + 1;//中心点之前和之后的元素
            while ((preI >= 0) && (sufI < oriArray.length) && (oriArray[preI] == oriArray[sufI])) {
                //两侧元素相等时 继续向两边进行判断
                preI--;
                sufI++;
            }
            //当前回文串的长度大于存储中的回文串的长度
            //为什么是减2呢？因为最后preI和sufI下标所在位置的值是不相同的 相同的是preI+1和sufI-1位置的值
            if (sufI - preI - 2 > end - first) {
                first = preI + 1;
                end = sufI - 1;
            }
        }
        //查找偶数位的回文串
        for (int i = 0; i < oriArray.length - 1; i++)//只需要到倒数第二位  因为偶数位的判断，需要判断随后一位是否与当前位相同
        {
            //相邻位置不相同
            if (oriArray[i + 1] != oriArray[i]) {
                continue;
            } else {
                //i和i+1为中心点  从i开始向两边进行判断
                int preI = i - 1, sufI = i + 2;
                while ((preI >= 0) && (sufI < oriArray.length) && (oriArray[preI] == oriArray[sufI])) {
                    //两侧元素相等时 继续向两边进行判断
                    preI--;
                    sufI++;
                }
                //当前回文串的长度大于存储中的回文串的长度
                if (sufI - preI - 2 > end - first) {
                    first = preI + 1;
                    end = sufI - 1;
                }
            }
        }
        //查找结束  将数组转化为字符串返回
        return String.valueOf(oriArray, first, end - first + 1);
    }

    /*************************
     * 求解字符串中的最长回文串-----动态规划法O(n^2)
     * 实现思路:用一个boolean类型的二维数组isPlalindrome[i][j] 来表示i到j之间的字符串是否回文
     * 其中 i>=j
     * 动态规划的初值就是  当i=j时，isPlalindrome[i][j]=true;
     * 动态规划的推导公式为  当i=j+1时，isPlalindrome[i][j]=(oriArray[i]==oriArray[j]),相邻两元素是否相等
     * 					当i>j+1时，需要判断i与j之间的子串是否是回文串,即
     * 							isPlalindrome[i][j]=(oriArray[i]==oriArray[j])&&isPlalindrome[i+1][j-1]
     * PS:状态矩阵赋值过程必须使用左下三角的形式  否则会产生误判 使用了未赋值的位置
     * @param original 要求解的字符串
     * @return 返回字符串中的最长回文串
     */
    public static String longestPalindrome3(String original) {
        //非空判断
        if ((original == null) || original.length() == 0) {
            return null;
        }
        //将字符串转换为字符数组
        char[] oriArray = original.toCharArray();
        int first = 0;
        int end = 0;//当前字符串中回文串的始末位置 包括末位置

        boolean[][] isPlalindrome = new boolean[oriArray.length][oriArray.length];
        //动归过程
        for (int i = 0; i < oriArray.length; i++) {
            for (int j = 0; j <= i; j++) {
			/*if(i==j)//同一位置
			{
				isPlalindrome[i][j]=true;
			}
			else if(j-i==1)//相邻元素
			{
				isPlalindrome[i][j]=(oriArray[i]==oriArray[j]);
			}*///合并为以下部分 这两部分都是可直接求解的
                if (i - j < 2) {
                    isPlalindrome[i][j] = (oriArray[i] == oriArray[j]);
                } else//不相邻的元素
                {
                    isPlalindrome[i][j] = ((oriArray[i] == oriArray[j]) && isPlalindrome[i - 1][j + 1]);
                }
                //一次动归过程完成 判断当前是否为回文串 如果是 长度是否大于当前存储的回文串
                if (isPlalindrome[i][j] && (i - j) > end - first) {
                    first = j;
                    end = i;
                }
            }
        }
        //查找结束  将数组转化为字符串返回
        return String.valueOf(oriArray, first, end - first + 1);
    }

    /****************************
     * 求解字符串中的最长回文串----马拉车方法(Manacher's Algorithm)  O(n)
     * 实现思路:和中心拓展法比较相似
     * 首先预处理原字符串
     * 在最开始添加特殊符号
     * 然后在字符串的每个字符之间以及开始和末尾添加另一种特殊符号，解决奇数回文串和偶数回文串的问题
     * 创建与处理后数组等长的辅助数组   assistArray[i]表示以changeArray[i]为中心的最长回文子串的半径，
     * 求解辅助数组引入mx和id两个变量 mx是回文串能延伸到的最右端的位置,id为能延伸到最右端的位置的那个回文子串的中心点位置
     *
     * @param original 要求解的字符串
     * @return 返回字符串中的最长回文串
     */
    public static String longestPalindrome4(String original) {
        //非空判断
        if ((original == null) || original.length() == 0) {
            return null;
        }
        //将字符串转换为字符数组
        char[] oriArray = original.toCharArray();
        int first = 0;
        int end = 0;//当前字符串中回文串的始末位置 包括末位置

        //对数组做预处理
        char[] changedArray = new char[oriArray.length * 2 + 3];//一个开始特殊符号  oriArray.length+1个填充符号 一个结尾符号
        int cIndex = 0;//修改后数组的遍历下标
        changedArray[cIndex++] = '$';//此处特殊符号选择美元符号
        for (int i = 0; i < oriArray.length; i++)//为修改后的数组赋值
        {
            changedArray[cIndex++] = '#';//填充特殊符号使用井号
            changedArray[cIndex++] = oriArray[i];
        }
        //最后添加#
        changedArray[cIndex++] = '#';//cIndex为changeArray的长度
        changedArray[cIndex++] = '%';

        //开始进行查找
        int[] assistArray = new int[cIndex];//定义等长辅助数组
        int mx = 0, id = 0;//辅助求解
        int resLen = 0, resCenter = 0;//回文串长度 中心点位置
        for (int i = 1; i < cIndex - 1; i++) {
            //(╯‵□′)╯︵┻━┻   马拉车太难了
            //核心部分
            if (mx > i)//当前求解位置在已经能够达到的位置之内
            {
                //当前位置的半径为
                //对称位置和半径
                //和 当前距离最右端的距离
                //中小的那一个
                assistArray[i] = Math.min(assistArray[2 * id - i], mx - 1);
            } else {
                assistArray[i] = 1;
            }
            //在已有回文串的基础上求解一个最大回文串
            while (changedArray[i + assistArray[i]] == changedArray[i - assistArray[i]])
                assistArray[i] = assistArray[i] + 1;
            //判断当前所能到达的最右侧的位置
            if (mx < i + assistArray[i]) {
                mx = i + assistArray[i];//可以到达为止的下一位置
                id = i;//可以到达最右侧位置的中心点  与最大回文串无直接联系
            }
            //当前求解的最大回文串和存储中的最大回文串 与上一部分的判断并无关联
            if (resLen < assistArray[i]) {
                resLen = assistArray[i];
                resCenter = i;
            }
        }
        //在改变后数组的中心位置和半径长度 转化为 原数组中的起始点坐标
        first = (resCenter - resLen) / 2;
        end = resLen - 1;
        //查找结束  将数组转化为字符串返回
        return String.valueOf(oriArray, first, end);
    }

    /**
     * 动态规划
     * 回文天然具有「状态转移」性质：一个长度严格大于 22 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。
     * <p>
     * 第 1 步：定义状态
     * dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。
     * <p>
     * 第 2 步：思考状态转移方程
     * 根据头尾字符是否相等，需要分类讨论：
     * <p>
     * <p>
     * dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
     * 说明：
     * <p>
     * 「动态规划」的「自底向上」求解问题的思路，很多时候是在填写一张二维表格。由于 s[i..j] 表示 s 的一个子串，因此 i 和 j 的关系是 i <= j，只需要填这张表格对角线以上的部分；
     * 看到 dp[i + 1][j - 1] 就需要考虑特殊情况：如果去掉 s[i..j] 头尾两个字符子串 s[i + 1..j - 1] 的长度严格小于 22（不构成区间），即 j - 1 - (i + 1) + 1 < 2j−1−(i+1)+1<2 时，整理得 j - i < 3j−i<3，此时 s[i..j] 是否是回文只取决于 s[i] 与 s[j] 是否相等。结论也比较直观：j - i < 3j−i<3 等价于 j - i + 1 < 4j−i+1<4，即当子串 s[i..j]s[i..j] 的长度等于 22 或者等于 33 的时候，s[i..j] 是否是回文由 s[i] 与 s[j] 是否相等决定。
     * 第 3 步：考虑初始化
     * 单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true。根据第 2 步的说明：当 s[i..j] 的长度为 22 时，只需要判断 s[i] 是否等于 s[j]，所以二维表格对角线上的数值不会被参考。所以不设置 dp[i][i] = true 也能得到正确结论。
     * <p>
     * 第 4 步：考虑输出
     * 一旦得到 dp[i][j] = true，就记录子串的「长度」和「起始位置」。没有必要截取，这是因为截取字符串也有性能消耗。
     * <p>
     * 第 5 步：考虑优化空间
     * 下面给出的「参考代码」，在填表的过程中，只参考了左下方的数值。事实上可以优化，但是增加了代码编写和理解的难度，丢失了可读性和可解释性。在这里不做优化空间；
     * 填表应该遵守这样的原则：总是先得到小子串是否是回文的结果，然后大子串才能参考小子串的判断结果，所以填表顺序很重要；
     * 建议自己动手，画一下表格，相信会对「动态规划」作为一种「表格法」有更好的理解。
     *
     * @param s
     * @return
     */
    public static String longestPalindrome5(String s) {
        // 特殊用例判断
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;

        // dp[i][j] 表示 s[i, j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        char[] charArray = s.toCharArray();

        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }


}
